/*************************************************************************
 * File Name:    Maximum_Subarray.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-8 14:28:25
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Maximum Subarray
 |
 | Find the contiguous subarray within an array (containing at least one number)
 | which has the largest sum.
 |
 | For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
 | the contiguous subarray [4,?1,2,1] has the largest sum = 6.
 |
 | click to show more practice.
 |
 | More practice:
 | If you have figured out the O(n) solution, try coding another solution using
 | the divide and conquer approach, which is more subtle.
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int maxSubArray(int A[], int n)
    {
        if (n <= 0) return 0;
        int ans = A[0];
        int sum = 0;
        
        for (int i = 0; i < n; ++i) {
            sum += A[i];
            ans = max(ans, sum);
            
            if (sum < 0) sum = 0;
        }
        return ans;
    }
};

